Number of submatrices that sum to target

Time: O(M^2xN); Space: O(N); hard

Given a matrix, and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1’, y1’, x2’, y2’) are different if they have some coordinate that is different: for example, if x1 != x1’.

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

Output: 4

Explanation:

  • The four 1x1 submatrices that only contain 0.

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0

Output: 5

Explanation:

  • The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Notes:

  • 1 <= len(matrix) <= 300

  • 1 <= len(matrix[0]) <= 300

  • -1000 <= matrix[i] <= 1000

  • -10^8 <= target <= 10^8

[1]:

import collections

class Solution1(object):
    """
    Time:  O(m^2*n), m is min(r, c), n is max(r, c)
    Space: O(n), which doesn't include transposed space
    """
    def numSubmatrixSumTarget(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: int
        """
        if len(matrix) > len(matrix[0]):
            return self.numSubmatrixSumTarget(map(list, zip(*matrix)), target)

        for i in range(len(matrix)):
            for j in range(len(matrix[i])-1):
                matrix[i][j+1] += matrix[i][j]

        result = 0
        for i in range(len(matrix)):
            prefix_sum = [0] * len(matrix[i])
            for j in range(i, len(matrix)):
                lookup = collections.defaultdict(int)
                lookup[0] = 1
                for k in range(len(matrix[j])):
                    prefix_sum[k] += matrix[j][k]
                    if prefix_sum[k] - target in lookup:
                        result += lookup[prefix_sum[k] - target]
                    lookup[prefix_sum[k]] += 1
        return result

[2]:

s = Solution1()
matrix = [[0,1,0], [1,1,1], [0,1,0]]
target = 0
assert s.numSubmatrixSumTarget(matrix, target) == 4
matrix = [[1,-1], [-1,1]]
target = 0
assert s.numSubmatrixSumTarget(matrix, target) == 5